#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//#pragma once
#define N 1000
typedef int SLDataType;//顺序表数据类型
//1. 顺序表->数组，并要求数据连续存储，不能有跳跃间隔

//静态顺序表
//静态特点：如果满了就不让插入
typedef struct SeqList1
{
    SLDataType a[N];
    int size; // 表示数组中存储了多少有效数据

}SL1;

//动态顺序表
typedef struct SeqList2
{
    SLDataType* a; // 指向动态开辟的数组
    unsigned int size; // 有效数据的个数
    unsigned int capacity; // 容量空间的大小
}SL2;

//接口函数
void SeqListPrint(SL2* ps);//打印顺序表
void SeqListInit(SL2* ps);//初始化
void SeqListDestroy(SL2* ps);//销毁
void SeqListPushBack(SL2* ps, SLDataType x);//尾插
void SeqListPopBack(SL2* ps);//尾删
void SeqListPushFront(SL2* ps, SLDataType x);//头插
void SeqListPopFront(SL2* ps);//头删
void SeqListCheckCapacity(SL2* ps);//检查是否需要扩容，如需要就扩容
int SeqListFind(SL2* ps, SLDataType x);//找到某个数据，返回下标
void SeqListInsert(SL2* ps, int pos, SLDataType x);//指定位置下标插入
void SeqListErase(SL2* ps, int pos);//指定位置下标删除

void TestSeqList1()
{
    SL2 s1;
    SeqListInit(&s1);
    SeqListPushBack(&s1, 1);
    SeqListPushBack(&s1, 2);
    SeqListPushBack(&s1, 3);
    SeqListPushBack(&s1, 4);
    SeqListPushBack(&s1, 5);
    SeqListPrint(&s1);
    SeqListPopBack(&s1);
    SeqListPopBack(&s1);
    SeqListPrint(&s1);

    SeqListDestroy(&s1);
}

void TestSeqList2()
{
    SL2 s1;
    SeqListInit(&s1);
    SeqListPushBack(&s1, 1);
    SeqListPushBack(&s1, 2);
    SeqListPushBack(&s1, 3);
    SeqListPushBack(&s1, 4);
    SeqListPushBack(&s1, 5);
    SeqListPrint(&s1);

    SeqListPushFront(&s1, 6);
    SeqListPushFront(&s1, 6);
    SeqListPushFront(&s1, 6);
    SeqListPushFront(&s1, 6);
    SeqListPushFront(&s1, 6);
    SeqListPrint(&s1);

    SeqListPopFront(&s1);
    SeqListPopFront(&s1);
    SeqListPopFront(&s1);
    SeqListPrint(&s1);

    SeqListDestroy(&s1);
}

int main()
{
    //TestSeqList1();
    TestSeqList2();
    return 0;
}

void SeqListPrint(SL2* ps)
{
    for(int i = 0; i < ps->size; i++)
    {
        printf("%d ", ps->a[i]);
    }
    printf("\n");
}

void SeqListInit(SL2* ps)
{
    ps->a = NULL;
    ps->size = ps->capacity = 0;
}

void SeqListDestroy(SL2* ps)
{
    free(ps->a);
    ps->a = NULL;
    ps->size = ps->capacity = 0;
}

void SeqListPushBack(SL2* ps, SLDataType x)//尾插
{
    SeqListCheckCapacity(ps);

    ps->a[ps->size] = x;
    ps->size++;
}

void SeqListPopBack(SL2* ps)
{
    //ps->a[ps->size - 1] = 0;//可以不要
    if(ps->size > 0)//assert(ps->size > 0);也可
    ps->size--;
}

void SeqListPushFront(SL2* ps, SLDataType x)
{
    SeqListCheckCapacity(ps);

    int end = ps->size - 1;
    while(end >= 0)
    {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[0] = x;
    ps->size++;
}

void SeqListPopFront(SL2* ps)
{
    assert(ps->size > 0);
    int begin = 1;
    while(begin < ps->size)
    {
        ps->a[begin - 1] = ps->a[begin];
        begin++;
    }
    ps->size--;
}

void SeqListCheckCapacity(SL2* ps)
{
    if(ps->size == ps->capacity)//没有空间或空间不足时扩容
    {
        int newcapacity = ps->capacity == 0? 4 : ps->capacity * 2;//二倍较为适中，也可选用其他大小
        SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
        //realloc在没有空间时相当于malloc，有空间时扩容空间
        if(tmp == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }

        ps->a = tmp;
        ps->capacity = newcapacity;
    }
}